Remotely-hosted computing services may be optimally designed to service a large number of customers. The customers may each submit to a computing service requests for the performance of computing tasks resulting. As a result, the resources of computing services become contested. In these multi-tenant computing environments, it is important to provide for a predictable customer experience such that the satisfaction of computing request is not unreasonably delayed. Furthermore, it is also important to ensure fairness such that one customer or a small set of customers do not overwhelm the system and “starve” other customers' of access to the computing resources. Additionally, it is also important to provide the customers with mechanisms to obtain additional computing capacity when needed.
It is often challenging to enable customers of a computing service to obtain additional capacity for backlogged computing work from other customers by trading or exchanging the capacity. It is also challenging to provide a marketplace for exchanging backlogged computing work capacity.